﻿#include "Debug.h"
#include "SeamCutter.h"

bool aLessThanB(Path* a, Path* b)
{
	return (a->getLength() < b->getLength());
}

SeamCutter::SeamCutter(DistortionModel* _dist, double _D, Options* opts)
{
	dist = _dist;
	D = _D;
	totalDistortion = dist->getOveralldistortion(opts->radius, opts->colType);	
	vector<VertexBase*> terminalVerts = getTerminalVertices();	

	if(terminalVerts.size() == 0 )
		return;

	vector<vector<Path*>> results = makeConnectedGraph(terminalVerts);

	list<Path*> sortedEdges;
	for(int i=0; i<terminalVerts.size(); i++)	
		for(int j=0; j<terminalVerts.size(); j++)	
			sortedEdges.push_front(results[i][j]);	
	sortedEdges.sort(aLessThanB);

	vector<Path*> mst;
	prims(sortedEdges, (int)terminalVerts.size(), mst);

	

	set<EdgeBase*> edgesMST;
	set<VertexBase*> vertsMST;
	for(int i=0; i<mst.size(); i++)
	{
		findpath(mst[i], minDists, next);
		mst[i]->getVertices(vertsMST, dist->getVertsMap());
 		mst[i]->getEdges(edgesMST, dist->getEdgeMap(), dist->getVertsMap());		
	}


	for(set<VertexBase*>::iterator i=vertsMST.begin(); i != vertsMST.end(); i++)		
		seamVerts.push_back((*i)->getNum());

	cout << "Seam Edges: " << endl;
	for(set<EdgeBase*>::iterator i=edgesMST.begin(); i != edgesMST.end(); i++)
	{
		seamEdges.push_back((*i)->getNum());
		cout << (*i)->getNum() << ", ";  
	}
	cout << endl;

	for(int i=0; i<terminalVerts.size(); i++)	
		for(int j=0; j<terminalVerts.size(); j++)		
			delete results[i][j]; 
}


vector<int> SeamCutter::getSeamVertices()
{
	return seamVerts;
}

vector<int> SeamCutter::getSeamEdges()
{
	return seamEdges;
}

void SeamCutter::prims(list<Path*> sortedEdges, int size, vector<Path*>& mst)
{	
	set<int> mstVerts;
	mstVerts.insert(sortedEdges.front()->getStart());

	//cout << "Path Weights: " << endl; 
	//for(list<Path*>::iterator i=sortedEdges.begin(); i!=sortedEdges.end(); i++)	
		//cout << "Start: " << (*i)->getStart() << " End: " << (*i)->getEnd() << " Length: " << (*i)->getLength() <<  endl;	

	list<Path*>::iterator i = sortedEdges.begin();
	while(mstVerts.size() != size)
	{
		if(i == sortedEdges.end())
			i = sortedEdges.begin();

		Path* possNewEdge = *i;
		if( (mstVerts.count(possNewEdge->getStart()) == 1) && (mstVerts.count(possNewEdge->getEnd()) == 0))
		{
			mst.push_back(possNewEdge);
			sortedEdges.erase(i);
			i = sortedEdges.begin();
			mstVerts.insert(possNewEdge->getEnd());
		}		
		i++;
	}
}

vector<vector<Path*>> SeamCutter::makeConnectedGraph(vector<VertexBase*> terminalVerts)
{
	vector<VertexBase*> verts = dist->getVertices();
	vector<EdgeBase*> edges = dist->getEdges();
	int dimensions = (int)verts.size();

	minDists.resize(dimensions, vector<double>(dimensions, 5000000));
	next.resize(dimensions, vector<int>(dimensions, -1));

	for(int i=0; i<dimensions; i++)	
		minDists[i][i] = 0;
	for(int i=0; i<edges.size(); i++)
	{
		minDists[edges[i]->getStart()->getNum()][edges[i]->getEnd()->getNum()] = edges[i]->getWeight();
		minDists[edges[i]->getEnd()->getNum()][edges[i]->getStart()->getNum()] = edges[i]->getWeight();
	}
	for(int k=0; k<dimensions; k++)	
		for(int i=0; i<dimensions; i++)		
			for(int j=0; j<dimensions; j++)			
				if( minDists[i][k] + minDists[k][j] < minDists[i][j] )
				{
			        minDists[i][j] = minDists[i][k] + minDists[k][j];
					next[i][j] = k;
				}
		
	vector<vector<Path*>> results(terminalVerts.size(), vector<Path*>(terminalVerts.size()));
	
	for(int i=0; i<terminalVerts.size(); i++)	
		for(int j=0; j<terminalVerts.size(); j++)
		{
			Path* path = new Path(terminalVerts[i]->getNum(), terminalVerts[j]->getNum());						
 			path->setLength(minDists[terminalVerts[i]->getNum()][terminalVerts[j]->getNum()]);
			results[i][j] = path;
		}
	
	return results;
}

void SeamCutter::findpath (Path* path, vector<vector<double>> minDists, vector<vector<int>> next)
{	
	int intermediate = next[path->getStart()][path->getEnd()];
	if(intermediate == -1)
		return;	
	else
	{
		Path* firstHalf = new Path(path->getStart(), intermediate);
		findpath(firstHalf, minDists, next);
		Path* secondHalf = new Path(intermediate, path->getEnd());
		findpath(secondHalf, minDists, next);
		path->add(firstHalf);
		path->add(intermediate);
		path->add(secondHalf);
		delete firstHalf;
		delete secondHalf;
	}    
}


SeamCutter::~SeamCutter(void)
{
}

bool compVerts(VertexBase* v1, VertexBase* v2)
{
	if(v1->getDistortion() >= v2->getDistortion())
		return true;
	return false;
}

vector<VertexBase*> SeamCutter::getTerminalVertices()
{
	vector<VertexBase*> verts = dist->getVertices();
	sort (verts.begin(), verts.end(), compVerts);
	
	double s=0;
	vector<VertexBase*> terminalVertices;
	
	for(int i=0; i<verts.size(); i++)
	{
		if(verts[i]->onBoundary()) 
			terminalVertices.push_back(verts[i]);
	}

	
	for(int i=0; s < totalDistortion-(D*totalDistortion) && i<verts.size(); i++)
	{				
		if(!verts[i]->onBoundary())
		{
			terminalVertices.push_back(verts[i]);
			s += verts[i]->getDistortion();		
		}
	}
	cout << "Resulting Distortion Reduction: " << s << endl;
	return terminalVertices;
}

